class Solution1312 {
    public int minInsertions(String s) {
        int n = s.length() ;
        char[] arr = s.toCharArray() ;
        // dp[i][j] : [i , j] 区间的最小插入数
        int[][] dp = new int[n][n] ;
        for(int i=n-1 ; i >= 0 ; i --){
            for(int j=i ; j < n; j ++){
                if(arr[i] == arr[j]){
                    if(i+1 < j){
                        dp[i][j] = dp[i+1][j-1] ;
                    }
                }else{
                    dp[i][j] = Math.min(dp[i+1][j] , dp[i][j-1])+1 ;
                }
            }
        }
        return dp[0][n-1] ;
    }
}